import numpy as np
from collections import Counter
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

class KNNClassifier:
    def __init__(self, k=3, distance_metric='euclidean'):
        """
        初始化KNN分类器
        :param k: 邻居数量（默认3）
        :param distance_metric: 距离度量方式（默认'euclidean'欧氏距离，可选'manhattan'曼哈顿距离）
        """
        self.k = k
        self.distance_metric = distance_metric
        self.X_train = None  # 训练特征
        self.y_train = None  # 训练标签

    def _euclidean_distance(self, x1, x2):
        """计算欧氏距离：sqrt(sum((x1-x2)^2))"""
        return np.sqrt(np.sum((x1 - x2) ** 2))

    def _manhattan_distance(self, x1, x2):
        """计算曼哈顿距离：sum(|x1-x2|)"""
        return np.sum(np.abs(x1 - x2))

    def fit(self, X, y):
        """
        训练KNN（仅存储数据，无实际训练过程）
        :param X: 训练特征矩阵 (n_samples, n_features)
        :param y: 训练标签 (n_samples,)
        """
        self.X_train = np.array(X)
        self.y_train = np.array(y)

    def predict(self, X):
        """
        预测样本类别
        :param X: 待预测样本矩阵 (n_samples, n_features)
        :return: 预测标签 (n_samples,)
        """
        X = np.array(X)
        predictions = [self._predict_single(x) for x in X]
        return np.array(predictions)

    def _predict_single(self, x):
        """预测单个样本的类别"""
        # 1. 计算当前样本与所有训练样本的距离
        if self.distance_metric == 'euclidean':
            distances = [self._euclidean_distance(x, x_train) for x_train in self.X_train]
        elif self.distance_metric == 'manhattan':
            distances = [self._manhattan_distance(x, x_train) for x_train in self.X_train]
        else:
            raise ValueError("距离度量仅支持 'euclidean' 或 'manhattan'")

        # 2. 对距离排序，获取前K个邻居的索引
        k_indices = np.argsort(distances)[:self.k]

        # 3. 获取K个邻居的类别
        k_neighbor_labels = self.y_train[k_indices]

        # 4. 投票表决（统计出现次数最多的类别）
        most_common = Counter(k_neighbor_labels).most_common(1)
        return most_common[0][0]
